package 简单.树;

import util.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 给定一个非空二叉树的根节点 root ,
 * 以数组的形式返回每一层节点的平均值。
 * 与实际答案相差 10-5 以内的答案可以被接受。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/average-of-levels-in-binary-tree/
 */
public class 二叉树的层平均值_637 {

    public static void main(String[] args) {

        System.out.println(averageOfLevels(new TreeNode(3)));

    }

    /**
     * 广度优先搜索
     *
     * @param root
     * @return
     */
    public static List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<>();
        if (root == null) return list;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            double sum = 0;
            int count = size;
            while (size-- > 0) {
                TreeNode curNode = queue.pollFirst();
                sum += curNode.val;
                if (curNode.left != null) queue.addLast(curNode.left);
                if (curNode.right != null) queue.addLast(curNode.right);
            }
            list.add(sum / count);
        }
        return list;
    }

}
